Materi Utama

Misteri Sistem Berulang (Modulo)

Berhenti berpikir bahwa Modulo sekadar "sisa hasil bagi". Mari melihatnya sebagai alat ajaib untuk melacak pola yang berulang tanpa batas.

Eksperimen 1: Apa yang Kamu Perhatikan?

Bayangkan hari ini adalah hari Senin.
- 7 hari dari sekarang adalah hari apa? (Senin)
- 14 hari dari sekarang? (Senin)
- 71 hari dari sekarang? Coba tebak tanpa menghitung manual hari per hari!

Buka Observasi
Pasti kamu membagi 71 dengan 7.
Kenapa? Karena nama hari "mereset" atau berputar kembali setiap kelipatan 7.
71 = (10 putaran penuh) + sisa 1 hari.
Putaran penuhnya tidak mengubah apapun (tetap Senin), yang penting hanyalah sisanya (1 hari setelah Senin = Selasa).

Intuisi Mendalam: Modulo sebagai Sistem Jam (Cyclic State)

Dalam pemrograman, operator modulo disimbolkan dengan %.
Saat kamu menulis X % N, jangan artikan sebagai "X dibagi N lalu cari sisanya".
Artikan secara mental sebagai: "Jika saya melangkah sebanyak X pada sebuah lingkaran yang ukurannya N, di titik mana saya akan berhenti?"

Contoh:

  • 14 % 12 = 2 (Jam 14.00 sama dengan Jam 2 siang)
  • 24 % 12 = 0 (Jam 24.00 sama dengan Jam 12/titik nol)
  • Modulo mengompres angka tak terhingga menjadi kelompok-kelompok kecil (0 sampai N-1).

Penghancur Miskonsepsi

Miskonsepsi: "Modulo hanya berguna kalau angkanya lebih besar dari pembaginya (contoh: 15 % 7)."

Kenyataan: Bagaimana jika 3 % 7? Hasilnya 3! Karena kamu melangkah 3 langkah di lingkaran ukuran 7, dan belum mencapai satu putaran penuh. Jadi kamu berhenti di titik 3.

Miskonsepsi Modulo Negatif: Di matematika murni, sisa bagi selalu positif. Tapi di bahasa C/C++, -5 % 3 akan menghasilkan -2!

Solusi OSN: Jika ada kemungkinan angkanya negatif, biasakan menulis ((A % N) + N) % N untuk memaksa hasilnya kembali ke siklus positif (berjalan mundur di jam, lalu disesuaikan kembali).

Lab: Visualisasi Wrapping Array (Batas Array)

Di OSN, Modulo sangat sering dipakai untuk membuat array tidak pernah Out of Bounds. Coba tekan tombol maju, lihat bagaimana indeks mereset saat melewati batas.

0
1
2
3
4
i = 0  →  Indeks Aktual = i % 5 = 0

Deep Transfer Learning: Modulo

Pendeteksi Pola Tersembunyi

OSN jarang secara gamblang meminta "hitung A modulo B". Modulo biasanya bersembunyi di balik kata-kata ini:

  • Wording: "Berputar kembali", "Bergiliran", "Hari ke-...", "Angka terakhir dari...".
  • Red Flag Constraint: "Lakukan simulasi pergerakan sebanyak 10^18 langkah". Brute force (loop 10^18 kali) akan butuh waktu bertahun-tahun (Time Limit Exceeded). Ini adalah sinyal mutlak untuk mencari panjang siklus dan menggunakan Modulo untuk melompati triliunan langkah yang berulang!
Uji Transfer & Reverse Thinking
  • Inverse Reasoning: Jika sebuah angka $X \pmod Y = 0$, apa kesimpulan mutlak yang bisa kamu ambil tentang $X$ dan $Y$? (Jawab keras-keras: Y pasti habis membagi X, yang berarti Y adalah faktor dari X).
  • What Changes? Bayangkan kamu sedang simulasi lompatan katak, tapi ukuran kolamnya (basis Modulo N) menyusut 1 petak setiap menit. Apakah rumus X % N yang statis masih bisa dipakai? Mengapa?
  • Koneksi Konsep: Algoritma Euclidean (FPB) yang akan kamu pelajari di Step 3 menggunakan esensi Modulo ini (pengurangan berulang) untuk membuang kelipatan yang tidak berguna. Modulo = Membuang putaran penuh.
Materi Utama

Atom Semesta Angka (Bilangan Prima)

Jangan hanya menghafal bahwa prima hanya bisa dibagi 1 dan dirinya sendiri. Mari pahami peran aslinya di dunia matematika.

Intuisi Visual: Membongkar Angka

Coba kita hancurkan angka 30 menjadi potongan terkecilnya dengan cara membaginya:
30 = 2 * 15 (15 masih bisa dihancurkan)
30 = 2 * 3 * 5 (Semuanya sudah tidak bisa dihancurkan lagi)

Angka 2, 3, dan 5 inilah yang disebut Bilangan Prima. Mereka adalah Atom pembentuk seluruh angka di dunia. Teorema Fundamental Aritmetika menyatakan bahwa setiap angka memiliki "DNA prima" atau sidik jari prima yang 100% unik! (Contoh: DNA dari 30 adalah 2, 3, dan 5).

Eksperimen 2: Kenapa Brute Force Lambat?

Kalau ditanya "Apakah 997 itu prima?", secara naluriah kamu akan mencoba membaginya dengan 2, 3, 4, 5... sampai 996.
Tapi OSN akan meminta kamu mengecek puluhan ribu angka sekaligus dalam 1 detik!

Rahasia Saringan Eratosthenes (Sieve)
Daripada mengecek "Apakah saya punya faktor?", Sieve membalik cara berpikirnya menjadi: "Mari hancurkan semua angka yang BUKAN prima dari awal!"

1. Kita ambil 2 (prima). Kita coret kelipatannya: 4, 6, 8, 10...
2. Kita ambil 3 (prima). Kita coret kelipatannya: 6 (sudah dicoret 2), 9, 12 (sudah dicoret 2), 15...

PERTANYAAN PENTING: Kapan kita mulai mencoret untuk kelipatan angka prima P?
Jawabannya: Selalu mulai dari P kuadrat (P * P)!
Mengapa? Karena kelipatan yang lebih kecil dari P kuadrat PASTI sudah dicoret oleh prima yang lebih kecil sebelumnya!
(Contoh: Saat kita di prima 5, kita tidak perlu mencoret 10, karena sudah dicoret oleh 2. Kita tidak perlu mencoret 15, karena sudah dicoret oleh 3. Kita langsung mulai coret dari 5*5 = 25!)

Buktikan Sendiri (Lab Sieve)

Perhatikan animasi di bawah. Saat proses mencapai angka 5, lihat angka apa yang pertama kali dicoret!

Penghancur Miskonsepsi

Miskonsepsi: "Angka 1 adalah bilangan prima, karena cuma bisa dibagi 1 dan dirinya sendiri."

Kenyataan: Definisi formalnya: Prima HARUS punya TEPAT 2 faktor yang BERBEDA. Angka 1 cuma punya 1 faktor. Jika 1 dianggap prima, "DNA prima" suatu angka tidak akan unik lagi (30 = 2*3*5 = 1*2*3*5 = 1*1*2*3*5 dst). Maka dari itu, 1 dibuang dari klub prima.

Miskonsepsi: "Semua bilangan prima pasti ganjil."

Kenyataan: Angka 2 adalah genap, dan dia adalah bilangan prima paling penting. Seringkali soal OSN mencoba menjebakmu dengan edge case genap tunggal ini!

Deep Transfer Learning: Prima & Sieve

Pendeteksi Pola Tersembunyi

OSN jarang secara langsung bilang "Gunakan Sieve". Waspadai pola ini:

  • Wording: "Berapa banyak faktor pembagi", "Hanya bisa dibagi oleh...", "Hitung jumlah bilangan yang coprime".
  • Red Flag Constraint: "Cek keprimaan untuk $10^5$ *query* (pertanyaan) di mana angka $N \le 10^7$". Memanggil fungsi isPrime(N) di dalam loop sebanyak ratusan ribu kali akan membuat kodemu Time Limit Exceeded. Solusinya: Lakukan pre-computation (buat array Sieve di awal program sebelum membaca *query*).
Uji Transfer & Reverse Thinking
  • Inverse Reasoning: Pada saat algoritma Sieve selesai, jika ada sebuah angka (misal 97) yang TIDAK PERNAH DICORET SAMA SEKALI oleh angka lain, apa kesimpulan mutlaknya? (Jawab: Itu artinya 97 tidak punya pembagi selain 1 dan dirinya sendiri. Ia selamat dari eliminasi karena ia Prima).
  • Why Is This Efficient? Sieve membalikkan logika! Daripada bertanya "Apakah 30 bisa dibagi angka lain?", Sieve berteriak: "Hai angka 2! Coret semua kelipatanmu (4, 6, 8, ... 30)!". Sieve membuang pekerjaan yang berulang (redundant work) karena kita hanya perlu mencoret, bukan melakukan operasi Modulo yang berat terus menerus.
  • Anti-Fake Understanding: Bayangkan Sieve tidak punya optimasi mulai dari $p^2$, dan kita mulai coret dari $p \times 2$. Pekerjaan apa yang dilakukan sia-sia berulang kali saat memproses angka Prima 5? (Jawab secara mental sebelum melihat Kuis nanti!)
Materi Utama

Membongkar GCD & LCM (FPB & KPK)

Sebelum kamu menghafal rumus, mari kita temukan rahasia dari potongan ubin dan tumpang tindih faktor.

Eksperimen 3: Memotong Persegi Panjang (Algoritma Euclidean)

Bayangkan kamu punya kertas berukuran 48 x 18 sentimeter. Kamu ingin memotong kertas ini menjadi persegi-persegi berukuran tepat sama tanpa ada sisa. Berapa ukuran persegi terbesar yang bisa kamu buat? Inilah inti dari GCD (Greatest Common Divisor / FPB).

Lihat Proses Tiling Euclidean
Algoritma Euclidean ditemukan ribuan tahun lalu. Intuisinya bukan "modulo", tapi pengurangan berulang (memotong ubin besar dengan ubin terbesar yang muat):

1. Ubin terpanjang adalah 48, terpendek adalah 18. Potong persegi `18x18` sebanyak mungkin dari `48`.
2. Kamu bisa memotong dua persegi `18x18`. Lebar yang terpakai = 36. Sisa lebarnya = 12 (Ini sama dengan 48 % 18).
3. Sekarang fokus ke sisa kertas berukuran 18 x 12.
4. Potong persegi `12x12` dari kertas itu. Sisa lebarnya = 6 (Ini sama dengan 18 % 12).
5. Sekarang sisa kertas berukuran 12 x 6.
6. Potong persegi `6x6`. Kamu dapat tepat dua persegi tanpa sisa! (12 % 6 = 0).

Karena tidak ada sisa lagi, ukuran ubin terakhir (6) adalah ukuran persegi terbesar yang bisa mengisi seluruh kertas 48x18. KITA MENEMUKAN GCD!

Kalkulator Tiling Euclidean

dan

Intuisi Visual: Kenapa Rumus KPK Dibagi FPB?

Rumus yang sering dihafal adalah: KPK(A, B) = (A * B) / FPB(A, B).
Tapi mengapa harus dibagi FPB? Mari bongkar DNA (faktor prima) mereka.

  • A = 12 (DNA: 2 * 2 * 3)
  • B = 18 (DNA: 2 * 3 * 3)
  • FPB (Irisan/Overlap): 2 * 3 = 6
  • Jika kita langsung kali (A * B):
  • (2 * 2 * 3) * (2 * 3 * 3) = 216

Perhatikan! Bagian DNA yang tumpang tindih (2 * 3) TERHITUNG DUA KALI kalau kita asal kalikan A * B.
Agar tidak dobel (karena KPK hanya butuh faktor minimum yang mencakup keduanya), kita harus "membuang" satu set duplikat tersebut dengan cara membaginya dengan FPB.

Penghancur Miskonsepsi

Miskonsepsi: "Angka yang lebih besar pasti punya FPB yang lebih besar dengan angka lain."

Kenyataan: FPB murni bergantung pada faktor prima yang sama. Contoh: FPB(1000, 7) adalah 1, karena 1000 dan 7 tidak punya DNA pembentuk yang sama (disebut Coprime).

Miskonsepsi Koding: "Langsung saja tulis (a * b) / gcd(a, b) untuk KPK."

Bahaya OSN (Integer Overflow): Jika $A$ dan $B$ besarnya $10^5$, maka $A \times B = 10^{10}$, ini melebihi batas Integer! Programmu akan error sebelum sempat membaginya dengan GCD. SELALU biasakan menulis: (A / gcd(A, B)) * B (Bagi dulu, baru kali).

Deep Transfer Learning: FPB & KPK

Pendeteksi Pola Tersembunyi

FPB dan KPK sering disamarkan dalam bentuk soal cerita:

  • Wording KPK: "Bertemu bersamaan lagi pada hari ke-", "Siklus terkecil di mana kedua mesin sinkron". (KPK adalah tentang membangun ke depan sampai menabrak titik yang sama).
  • Wording FPB: "Membagi sama rata ke dalam wadah terbanyak", "Memotong dengan ukuran balok terbesar tanpa sisa". (FPB adalah tentang membongkar struktur mencari material dasar yang sama).
  • Red Flag Constraint: Mencari KPK dengan mengalikan `A` dan `B` lalu *brute force* mengecek satu per satu apakah bisa dibagi. Langsung gunakan rumus (A / FPB) * B!
Uji Transfer & Reverse Thinking
  • Inverse Reasoning 1: Jika diketahui `FPB(A, B) = 1` (mereka disebut Coprime), apa yang terjadi dengan nilai KPK mereka? (Jawab: Karena tidak ada DNA yang sama untuk dibuang, maka `KPK(A, B) = A * B`).
  • Inverse Reasoning 2: Jika FPB(A, B) = A, apa hubungan matematis antara A dan B? (Jawab: A pasti adalah faktor dari B, contoh FPB(5, 15) = 5).
  • Kebiasaan Kognitif OSN: Biasakan melihat angka bukan sebagai nilai akhir (misal 216), tapi sebagai tumpukan faktor (2*2*2*3*3*3). Ini akan membuatmu bisa "melihat tembus pandang" saat mencari irisan/gabungan antar angka raksasa.

Uji Penguasaan Akhir (Anti-Fake Understanding)

Jangan biarkan dirimu terjebak "Ilusi Paham"! Sebelum mengklik tombol Kuis di bawah, jawab pertanyaan ini dengan suara lantang. Bisakah kamu menjelaskannya ke temanmu tanpa melihat catatan?

  1. Jelaskan kenapa kita pakai Modulo saat mencari sisa gerakan pion dari 10^18 langkah!
  2. Jelaskan kenapa algoritma Sieve of Eratosthenes mencoret mulai dari nilai $p^2$, bukan dari $p \times 2$!
  3. Jelaskan secara visual pakai perumpamaan ubin lantai, bagaimana Algoritma Euclidean menemukan FPB!
  4. Kenapa rumus KPK adalah A dikali B lalu dibagi FPB? Kenapa harus dibagi?

Jika ada satu saja yang tidak bisa kamu jelaskan ALASANNYA secara logis, jangan lanjut. Scroll ke atas dan ulangi eksperimennya!

Modul Minggu 3 Selesai!
Kerjakan Kuis Minggu 3